package org.example.two.sort;

import org.example.two.Example;
import org.example.two.datatype.MaxPQ;

/**
 * 堆排序
 * @outher 刘旭
 * @date 2024/6/5 11:01
 */
public class Pile  extends Example {
    @Override
    public void sort(Comparable[] a){
        int N = a.length;
        for (int i = N/2; i >=0 ; i--) {
            sink(a,i,N);
        }
        for (int i = N-1; i > 0 ; i--) {
            exch(a,0,i);
            sink(a,0,i);
        }

    }

    private boolean less(Comparable[] pq,int i , int j){
        return pq[i].compareTo(pq[j])<0;
    }
    // 交换两个元素的位置
    @Override
    public void exch(Comparable[] pq,int i ,int j){
        Comparable t = pq[i];
        pq[i] = pq[j];
        pq[j] = t;
    }
    // 将元素下沉到合适的位置
    public void sink(Comparable[] pq,int k,int N){
        // 如果当前元素有子元素，并且当前元素小于子元素中的较大者，则交换它们的位置，然后继续下沉
        while (k*2+1<N){
            int j=k*2+1;
            if (j+1<N && less(pq,j,j+1)){
                j++;
            }
            if (!less(pq,k,j)){
                break;
            }
            exch(pq,k,j);
            k=j;
        }
    }

}
